package Solution125_150;

import common.ListNode;
import org.junit.Test;

public class Solution147链表插入排序 {
    public ListNode insertionSortList1(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode node=new ListNode(0);
        node.next=new ListNode(head.val);
        while (head.next!=null){
            ListNode curNode=new ListNode(head.next.val);
            connectNode(node,curNode);
            head=head.next;
        }
        return node.next;
    }

    private void connectNode(ListNode node,ListNode curNode){
        while (node.next!=null){
            if(node.next.val>curNode.val){
                ListNode temp=node.next;
                node.next=curNode;
                curNode.next=temp;
                return;
            }
            node=node.next;
        }
        node.next=curNode;
        curNode.next=null;
    }

    /**
     * 别人写的优解
     * @param head
     * @return
     */
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode(0);
        ListNode pre = dummy;
        ListNode cur = head;
        while (cur != null) {
            ListNode tmp = cur.next;
            while (pre.next != null && pre.next.val < cur.val) pre = pre.next;
            cur.next = pre.next;
            pre.next = cur;
            pre = dummy;
            cur = tmp;
        }
        return dummy.next;
    }


    @Test
    public void test(){
        //4->2->1->3
        ListNode listNode1=new ListNode(4);
        ListNode listNode2=new ListNode(2);
        ListNode listNode3=new ListNode(1);
        ListNode listNode4=new ListNode(3);
      //  ListNode listNode5=new ListNode(5);
        listNode1.next=listNode2;
        listNode2.next=listNode3;
        listNode3.next=listNode4;
       // listNode4.next=listNode5;

        ListNode result=insertionSortList(listNode1);
        System.out.println(result);
    }
}
